import java.util.Arrays;

/**
 * @author luoqingbo
 * @create 2024/5/7 9:40
 */
public class Leetcode1463 {
    public static void main(String[] args) {
        //int[][] grid = {{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
        //int[][] grid = {{1, 0, 0, 0, 0, 0, 1}, {2, 0, 0, 0, 0, 3, 0}, {2, 0, 9, 0, 0, 0, 0}, {0, 3, 0, 5, 4, 0, 0}, {1, 0, 2, 3, 0, 0, 6}};
        //int[][] grid = {{1, 0, 0, 3}, {0, 0, 0, 3}, {0, 0, 3, 3}, {9, 0, 3, 3}};
        int[][] grid = {{1, 1}, {1, 1}};
        int ans = cherryPickup(grid);
        System.out.println(ans);
    }

    public static int cherryPickup(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][][][] memo = new int[row][col][row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < row; k++) {
                    Arrays.fill(memo[i][j][k], -2);
                }
            }
        }
        int ans = dfs(0, 0, 0, col - 1, grid, memo);
        return ans < 0 ? 0 : ans;
    }

    private static int dfs(int x1, int y1, int x2, int y2, int[][] grid, int[][][][] memo) {
        int row = grid.length;
        int col = grid[0].length;
        //越界判断
        if (x1 >= row || y1 >= col || y1 < 0 || x2 >= row || y2 >= col || y2 < 0) {
            return -1;
        }
        //判断是否记忆
        if (memo[x1][y1][x2][y2] != -2) {
            return memo[x1][y1][x2][y2];
        }
        //判断终点
        if (x1 == row - 1 && x2 == row - 1) {
            if (y1 == y2) {
                return grid[x1][y1];
            } else {
                return grid[x1][y1] + grid[x2][y2];
            }
        }
        int max = Integer.MIN_VALUE;
        //方向
        int[][] dir = {{1, -1}, {1, 0}, {1, 1}};
        for (int i = 0; i < dir.length; i++) {
            for (int j = 0; j < dir.length; j++) {
                int temp = dfs(x1 + dir[i][0], y1 + dir[i][1], x2 + dir[j][0], y2 + dir[j][1], grid, memo);
                max = temp > max ? temp : max;
            }
        }
        max += ((x1 == x2 && y1 == y2) ? grid[x1][y1] : grid[x1][y1] + grid[x2][y2]);
        memo[x1][y1][x2][y2] = max;
        return memo[x1][y1][x2][y2];
    }
}
